There are many design and manufacturing processes in which substantially two dimensional parts-to-be-assembled are initially laid out on and then cut from planes or sheet stock. For example, leather shoes, clothing, pocketbooks, and automobile and furniture upholstery are often formed from a plurality of panels, or parts, cut from a cowhide. After cutting of the panels for such an article, conventional seam joining techniques, such as sewing, are used to assemble the panels to form the finished article. Clothing, upholstery and many other articles of other materials are similarly designed and manufactured in a similar manner. Such other articles include body parts for automobiles, for example, hoods or fenders, which may be stamped from metal sheets, and then subsequently shaped to form the final part configuration. Numerous other articles are similarly manufactured from planar sheets as well.
In the manufacture of all of these parts, it is important to minimize the waste which remains after the parts are cut from the sheet stock. While in some cases, where the waste can be re-used, such as in the case of sheet metal, this factor is of lesser importance, there are many cases where the minimization of waste is of critical importance to the commercial viability of a product. The latter cases particularly include shoe manufacture, where the cost of materials, for example cowhides or synthetic materials, is very high.
In view of such cost considerations, manufacturing processes generally include attempts to minimize waste. However, the conventional attempts at such minimization have been relatively ineffective. In the leather shoe industry, for example, parts are often manually die cut from cowhides, where the die is manually placed on the hide by skilled (or relatively unskilled) workers, typically resulting in maximum yields in the 50–60% range for the typical irregularly shaped parts. In recent years, computer controlled layout of parts on a hide have been achieved, resulting in typical yields as high as the 60–70% range.
In U.S. Pat. No. 4,210,041, the present inventors disclosed a method for laying out, or nesting, a plurality of identical irregular non-polygonal rounded pieces on a parallel edge-bounded sheet material with relatively little waste. In accordance with the method of that patent, the salient points of the part boundary are connected by straight lines to box the part boundary in a plane polygonal figure. Then, pairs of such plane polygonal figures are pairwise positioned to within a plane closed parallelogram. Finally, a plurality of such parallelogram are arranged side-by-side to define a multiple repeat pattern of objects equal in width to the planar sheet from which the parts are to be cut. A nest constructed in accordance with U.S. Pat. No. 4,210,041 does offer improvement in nesting over prior art techniques; however, the resulting nests are still less than optimal.
Part I of the disclosure as set forth above discloses improvements in nesting of two dimensional objects. That application is incorporated by reference herein.
Further, there is a need to nest three dimensional objects in a target volume.
Typically three dimensional objects are manually, or by machine, packed in target volumes with less than optimal techniques. It would be advantageous in many industries to use an optimal technique. For example in the container shipping industry, containers are packed with objects to be shipped using manually determined placement of the object, generally starting from one border of the container and adding objects one at a time until the container is “full”. There are of course cases where an optimized process is easily realized, such as where identical cubic objects are placed in a container having dimensions which are integer multiples of the dimensions of each side of the cubic object. Generally, however, the cubic shape and those container dimension constraints are not present and the conventional packaging methods result in a “filled” container with substantial void regions between the packed objects.
It is an object of the present invention to provide an improved method and system for defining a nest of three dimensional objects.
It is another object to provide an improved method and apparatus for packaging a plurality of three dimensional parts in a target volume.